P2146 [NOI2015]软件包管理器

这其实是一道树链剖分的板题，难在读题...

借一下洛谷的图：（将边看成无向的）

如果理解了题目，我们会发现：

1.安装一个软件$u$需要将$u$号软件到$0$号软件的路径上所有未安装的软件安装。

2.删除一个软件$u$需要将以$u$为根的子树上所有安装的软件删除。

其实它们分别是路径修改和子树修改，树链剖分后线段树维护区间安装的软件个数就好了。

#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
#define ls x << 1
#define rs x << 1 | 1
#define INF 0x3f3f3f3f

const int MAXN = 100000;
int n , q , cnt;
int Fa[ MAXN + 5 ] , Size[ MAXN + 5 ] , Depth[ MAXN + 5 ] , Heaviest_son[ MAXN + 5 ];
int Dfn[ MAXN + 5 ] , Top[ MAXN + 5 ] , Rank[ MAXN + 5 ];
vector< int > Graph[ MAXN + 5 ];

struct Point{
	int l , r , num , Lazy;
};
struct Segment_Tree{
	Point Tree[ 4 * MAXN + 5 ];
	void Build( int x , int l , int r ) {
		Tree[ x ].l = l , Tree[ x ].r = r , Tree[ x ].Lazy = -1 , Tree[ x ].num = 0;
		if( l == r )
			return;
		int Mid = ( l + r ) / 2;
		Build( ls , l , Mid );
		Build( rs , Mid + 1 , r );
	}
	void Pushdown( int x ) {
		if( Tree[ x ].Lazy == 0 ) {
			Tree[ ls ].num = Tree[ rs ].num = 0;
			Tree[ ls ].Lazy = Tree[ rs ].Lazy = 0;
			Tree[ x ].Lazy = -1;
		}
		if( Tree[ x ].Lazy == 1 ) {
			Tree[ ls ].num = ( Tree[ ls ].r - Tree[ ls ].l + 1 );
			Tree[ rs ].num = ( Tree[ rs ].r - Tree[ rs ].l + 1 );
			Tree[ ls ].Lazy = Tree[ rs ].Lazy = 1;
			Tree[ x ].Lazy = -1;
		}
	}
	void Insert( int x , int l , int r , int k ) {
		if( r < Tree[ x ].l || Tree[ x ].r < l ) 
			return;
		if( l <= Tree[ x ].l && Tree[ x ].r <= r ) {
			Tree[ x ].num = k ? ( Tree[ x ].r - Tree[ x ].l + 1 ) : 0;
			Tree[ x ].Lazy = k; 
			return;
		}
		Pushdown( x );
		Insert( ls , l , r , k );
		Insert( rs , l , r , k );
		Tree[ x ].num = ( Tree[ ls ].num + Tree[ rs ].num );
	}
	int Find( int x , int l , int r ) {
		if( r < Tree[ x ].l || Tree[ x ].r < l ) 
			return 0;
		if( l <= Tree[ x ].l && Tree[ x ].r <= r )
			return Tree[ x ].num;
		Pushdown( x );
		return Find( ls , l , r ) + Find( rs , l , r );
	}
	
	int Query_ins( int u , int v ) {
		int Ans = 0;
		while( Top[ u ] != Top[ v ] ) {
			if( Depth[ Top[ u ] ] < Depth[ Top[ v ] ] )
				swap( u , v );
			Ans += ( Depth[ u ] - Depth[ Top[ u ] ] + 1 ) - Find( 1 , Dfn[ Top[ u ] ] , Dfn[ u ] );
			Insert( 1 , Dfn[ Top[ u ] ] , Dfn[ u ] , 1 );
			
			u = Fa[ Top[ u ] ];
		}
		if( Depth[ u ] > Depth[ v ] )
			swap( u , v );
		Ans += ( Depth[ v ] - Depth[ u ] + 1 ) - Find( 1 , Dfn[ u ] , Dfn[ v ] );
		Insert( 1 , Dfn[ u ] , Dfn[ v ] , 1 );
		return Ans;
	}
	int Query_uni( int u ) {
		int Ans = Find( 1 , Dfn[ u ] , Dfn[ u ] + Size[ u ] - 1 );
		Insert( 1 , Dfn[ u ] , Dfn[ u ] + Size[ u ] - 1 , 0 );
		return Ans;
	}
}Tree;

void dfs1( int u , int fa ) {
	Fa[ u ] = fa , Depth[ u ] = Depth[ fa ] + 1 , Size[ u ] = 1;
	
	for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
		int v = Graph[ u ][ i ];
		if( v == fa ) continue;
		dfs1( v , u );
		Size[ u ] += Size[ v ];
		if( Size[ Heaviest_son[ u ] ] < Size[ v ] )
			Heaviest_son[ u ] = v;
	}
}
void dfs2( int u , int top ) {
	Top[ u ] = top , Dfn[ u ] = ++ cnt , Rank[ cnt ] = u;
	
	if( !Heaviest_son[ u ] ) return;
	dfs2( Heaviest_son[ u ] , top );
	for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
		int v = Graph[ u ][ i ];
		if( !Dfn[ v ] ) dfs2( v , v );
	}
}

int u , v;
char op[ 20 ];
int main( ) {
	scanf("%d",&n);
	for( int i = 2 ; i <= n ; i ++ ) {
		scanf("%d",&v);v ++;
		Graph[ i ].push_back( v );
		Graph[ v ].push_back( i );
	}
	dfs1( 1 , 0 );
	dfs2( 1 , 1 );
	
	Tree.Build( 1 , 1 , n );
	scanf("%d",&q);
	for( int i = 1 ; i <= q ; i ++ ) {
		scanf("%s %d",op,&u);u ++;
		if( op[ 0 ] == 'i' )
			printf("%d\n", Tree.Query_ins( 1 , u ) );
		if( op[ 0 ] == 'u' )
			printf("%d\n", Tree.Query_uni( u ) );
	}
	return 0;
}